package leetcode_数与位._01数字的位操作;

/**
 * @author yzh
 * @data 2021/3/25 22:02
 * 汉明距离总和
 * 调用 461 的方法，两重循环 --- 超时
 * 最大 32 位，第一层循环 32 次
 * 按位来算，每一位的汉明距离 = 所有 1 的个数 * 所有 0 的个数
 */
public class _477_汉明距离总和 {
    public static void main(String[] args) {
        System.out.println(new _477_汉明距离总和().totalHammingDistance_perfect(new int[]{4, 14, 2}));
    }

    public int totalHammingDistance_perfect(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int oneCount = 0, zeroCount = 0;
            for (int j = 0; j < nums.length; j++) {
                if (i != 0) nums[j] = nums[j] >> 1;
                int tem = nums[j] & 1;
                if (tem == 0) ++zeroCount;
                else ++oneCount;
            }
            ans += zeroCount * oneCount;
        }
        return ans;
    }

    public int totalHammingDistance(int[] nums) {
        int len = nums.length, ans = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                ans += hammingDistance(nums[i], nums[j]);
            }
        }
        return ans;
    }

    public int hammingDistance(int x, int y) {
        x = x ^ y;
        int ans = 0;
        while (x != 0) {
            int tem = x & 1;
            if (tem == 1) ++ans;
            x = x >> 1;
        }
        return ans;
    }
}
